package 数组和链表.linklist;

import 抽象数据类型.ListNode;

public class CircularLinkedList {
    private ListNode first = new ListNode();
    private int length;


    public CircularLinkedList() {

    }
    //构造循环链表

    public CircularLinkedList CircularLinkedListHead() {
        ListNode headNode = first;
        if (first.next != null) {
            ListNode currentNode = headNode.next;
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            currentNode.next = headNode.next;
        }
        return new CircularLinkedList(headNode, length);
    }

    public CircularLinkedList CircularLinkedListTail() {
        ListNode headNode = first;
        if (first.next != null) {
            ListNode currentNode = headNode.next;
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            currentNode.next = headNode.next;
            headNode.next = currentNode;
        }
        return new CircularLinkedList(headNode, length);
    }

    public CircularLinkedList(ListNode first, int length) {
        this.first = first;
        this.length = length;
    }


    public CircularLinkedList InitList(Object[] L) {
        for (Object o : L) {
            ListInsert(o, length);
        }
        return new CircularLinkedList(first, length);
    }


    public void DestroyList() {
        first = null;
    }


    public boolean ListEmpty() {
        if (first.next == null) {
            return true;
        }
        return false;
    }


    public int ListLength() {
        int count = 0;
        ListNode current = first.next;
        while (current != null) {
            current = current.next;
            count++;
        }
        return count;
    }


    public Object GetElem(int i) {
        if (i < 0 || i >= this.length) {
            throw new IndexOutOfBoundsException("下表越界");
        }
        int index = 0;
        ListNode current = first.next;
        while (true) {
            if (index == i) {
                return current;
            }
            current = current.next;
            index++;
        }
    }


    public int LocateElem(Object e) {
        ListNode current = first.next;
        int index = 0;
        while (current != null) {
            if (current.getVal() == (int) e) {
                return index;
            }
            current = current.next;
            index++;
        }
        return 0;
    }


    public Object PirorElem(Object e) {
        ListNode current = first.next;
        ListNode priorNode;
        int index = 0;
        while (current != null) {
            priorNode = current;
            if (current.getVal() == (int) e && index != 0) {
                return priorNode;
            }
            current = current.next;
            index++;
        }
        return null;
    }


    public Object nextElem(Object e) {
        ListNode current = first.next;
        while (current != null) {
            if (current.getVal() == (int) e) {
                if (current.next != null) {
                    return current.next;
                }
            }
            current = current.next;

        }
        return null;
    }


    public void ListInsert(Object e, int i) {
        if (i < 0 || i > length) {
            throw new IndexOutOfBoundsException("数组越界");
        }

        int index = 0;
        ListNode priorNode = first;
        ListNode current = first.next;
        ListNode insertNode = new ListNode((int) e);
        if (current == null) {
            first.next = insertNode;
        } else {
            while (current.next != null) {
                if (index == i) {
                    priorNode.next = insertNode;
                    insertNode.next = current.next;
                    return;
                }
                priorNode = current;
                current = current.next;
                index++;
            }
            if (current.next == null) {
                current.next = insertNode;
            }
        }
        this.length++;
    }


    public Object ListDelete(int i) {

        if (i < 0 || i >= length) {
            throw new IndexOutOfBoundsException("数组越界");
        }
        int index = 0;
        ListNode priorNode = first;
        ListNode current = first.next;
        while (current != null) {
            if (index == i) {
                priorNode.next = current.next;
            }
            priorNode = current;
            current = current.next;
            index++;
        }

        this.length--;
        return current;
    }


    public void ListObjectraverse() {
        int count = 40;
        ListNode current = first.next;
        while (current != null && count >= 0) {
            count--;
            System.out.print(current.getVal() + "\t");
            current = current.next;
        }

    }


    public void Replace(Object e, int i) {
        ListNode current = first.next;
        int index = 0;
        while (current != null) {
            if (index == i) {
                current.setVal((int) e);
            }
            current = current.next;
            index++;
        }
    }

    static class MainTest {
        public static void main(String[] args) {
            Object[] a = {1, 3, 4, 5, 9};
            Object[] b = {2, 4, 6, 10};
            CircularLinkedList AL = (CircularLinkedList) (new CircularLinkedList()).InitList(a);
            CircularLinkedList BL = (CircularLinkedList) (new CircularLinkedList()).InitList(b);
         /*   LinkedList circularLinkedListHead = AL.CircularLinkedListHead();

            circularLinkedListHead.ListObjectraverse();*/

            CircularLinkedList circularLinkedListTailAl = AL.CircularLinkedListTail();
            CircularLinkedList circularLinkedListTailBl = BL.CircularLinkedListTail();
            circularLinkedListTailAl.ListObjectraverse();
            System.out.println();
            MergeListTail(circularLinkedListTailAl, circularLinkedListTailBl).ListObjectraverse();
        }

        private static CircularLinkedList MergeListTail(CircularLinkedList La, CircularLinkedList Lb) {
            ListNode LaListNode = La.first;
            ListNode LbListNode = Lb.first;
            ListNode LaTailNode = LaListNode.next;
            ListNode LbTailNode = LbListNode.next;
            ListNode tempAHead = LaTailNode.next;//头节点
            LaTailNode.next = LbTailNode.next;
            LbTailNode.next = tempAHead;
            La.first = Lb.first;
            return La;

        }
    }

    static class Main {
        public static void main(String[] args) {
            Object[] a = {1, 3, 4, 5, 9};
            Object[] b = {2, 4, 6, 10};
            CircularLinkedList AL = (CircularLinkedList) (new CircularLinkedList()).InitList(a);
            CircularLinkedList BL = (CircularLinkedList) (new CircularLinkedList()).InitList(b);
            AL.ListObjectraverse();
            System.out.println();
            BL.ListObjectraverse();
            /*AL.ListInsert(1, 0);
            System.out.println();
            System.out.println(AL.length);
            AL.ListDelete(4);
            AL.ListObjectraverse();*/
            System.out.println();
            MergerListOne((AL), BL).ListObjectraverse();
        }


        private static CircularLinkedList MergerList(CircularLinkedList La, CircularLinkedList Lb) {
            CircularLinkedList Lc = new CircularLinkedList();
            ListNode currentC = Lc.first;
            ListNode currentA = La.first.next;
            ListNode currentB = Lb.first.next;
            while (currentA != null && currentB != null) {
                if (currentA.getVal() <= currentB.getVal()) {
                    currentC.next = currentA;
                    currentA = currentA.next;
                } else {
                    currentC.next = currentB;
                    currentB = currentB.next;
                }
                currentC = currentC.next;
            }
            return Lc;
        }

        private static CircularLinkedList MergerListOne(CircularLinkedList La, CircularLinkedList Lb) {
            ListNode currentA = La.first.next;
            ListNode currentB = Lb.first.next;
            ListNode prior = La.first;
            while (currentA != null && currentB != null) {
                if (currentA.getVal() >= currentB.getVal()) {
                    ListNode insertNode = new ListNode(currentB.getVal());
                    prior.next = insertNode;
                    insertNode.next = currentA;
                    currentB = currentB.next;
                } else {
                    currentA = currentA.next;
                }
                prior = prior.next;
            }
            if (currentB != null) {
                prior.next = currentB;
            }
            return La;
        }

    }
}
